Search results for "Tamari lattice"

showing 4 items of 4 documents

A Motzkin filter in the Tamari lattice

2015

The Tamari lattice of order n can be defined on the set T n of binary trees endowed with the partial order relation induced by the well-known rotation transformation. In this paper, we restrict our attention to the subset M n of Motzkin trees. This set appears as a filter of the Tamari lattice. We prove that its diameter is 2 n - 5 and that its radius is n - 2 . Enumeration results are given for join and meet irreducible elements, minimal elements and coverings. The set M n endowed with an order relation based on a restricted rotation is then isomorphic to a ranked join-semilattice recently defined in Baril and Pallo (2014). As a consequence, we deduce an upper bound for the rotation distan…

Discrete mathematicsMathematics::CombinatoricsBinary tree010102 general mathematicsLattice (group)0102 computer and information sciences[ MATH.MATH-CO ] Mathematics [math]/Combinatorics [math.CO]01 natural sciencesUpper and lower boundsTheoretical Computer ScienceCombinatoricsJoin and meet010201 computation theory & mathematics[MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO]Discrete Mathematics and CombinatoricsOrder (group theory)Ideal (order theory)0101 mathematicsFilter (mathematics)Tamari latticeComputingMilieux_MISCELLANEOUSMathematics
researchProduct

Generating binary trees by Glivenko classes on Tamari lattices

2003

Using algebraic-theoretic results, we give an algorithm for generating binary trees within Glivenko classes in Tamari lattices. Tamari lattices are lattices of binary trees endowed by the well-known rotation transformation.

Discrete mathematicsMathematics::CombinatoricsBinary treeHigh Energy Physics::LatticeGraph theoryComputer Science ApplicationsTheoretical Computer ScienceCombinatoricsLattice (order)Signal ProcessingTamari latticeRotation (mathematics)Information SystemsMathematicsInformation Processing Letters
researchProduct

The Rotation χ-Lattice of Ternary Trees

2001

This paper generalizes to k-ary trees the well-known rotation transformation on binary trees. For brevity, only the ternary case is developped. The rotation on ternary trees is characterized using some codings of trees. Although the corresponding poset is not a lattice, we show that it is a χ-lattice in the sense of Leutola–Nieminen. Efficient algorithms are exhibited to compute meets and joins choosen in a particular way.

Discrete mathematicsNumerical AnalysisBinary treeTernary treeWeight-balanced treeComputer Science ApplicationsTheoretical Computer ScienceCombinatoricsComputational MathematicsComputational Theory and MathematicsTernary search treeTernary operationTamari latticePartially ordered setRotation (mathematics)SoftwareMathematicsComputing
researchProduct

Motzkin subposets and Motzkin geodesics in Tamari lattices

2014

The Tamari lattice of order n can be defined by the set D n of Dyck words endowed with the partial order relation induced by the well-known rotation transformation. In this paper, we study this rotation on the restricted set of Motzkin words. An upper semimodular join semilattice is obtained and a shortest path metric can be defined. We compute the corresponding distance between two Motzkin words in this structure. This distance can also be interpreted as the length of a geodesic between these Motzkin words in a Tamari lattice. So, a new upper bound is obtained for the classical rotation distance between two Motzkin words in a Tamari lattice. For some specific pairs of Motzkin words, this b…

GeodesicSemilattice0102 computer and information sciences[INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM][ MATH.MATH-CO ] Mathematics [math]/Combinatorics [math.CO]01 natural sciencesUpper and lower boundsTheoretical Computer ScienceCombinatorics[MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO]0101 mathematicsComputingMilieux_MISCELLANEOUSMathematicsDiscrete mathematicsMathematics::Combinatorics010102 general mathematics[ INFO.INFO-DM ] Computer Science [cs]/Discrete Mathematics [cs.DM]Join (topology)Computer Science ApplicationsJoin and meet010201 computation theory & mathematicsSignal ProcessingMotzkin numberTamari latticeRotation (mathematics)Computer Science::Formal Languages and Automata TheoryInformation Systems
researchProduct